"""
Author: Yanrui Hu
Date: 2023/3/14
Description: 构造指定回文子串个数的字符串
Keyword: 回文字符串, 回文子串, 「装仓算法」, 指定规则的字符串构造
Version: 1.0.0
Reference: CZY聊天记录

题目描述：
给定一个整数x，请你构造一个仅由'r'、'e'、d'三种字符组成的字符串，其中回文子串的数量恰好为x。字符串的长度不得超过10^5。
1 <= x <= 10^9

输出一个仅由'r'、"e'、'd'三种字符组成的字符串，长度不得超过10^5。有多解时输出任意即可。
"""

import math
from typing import List


def solv_n(x: int) -> int:
    '''
    求解方程 n(n+1) <= 2*x, 找到满足条件的最大的整数n
    (n + 1/2 ) **2 <= 2*x + 1/4
    '''
    root = math.sqrt(x*2 + 1/4)
    return math.floor(root - 1/2)


def binning_algo(x: int) -> List[int]:
    '''
    ### 「装仓算法」
    寻找到一个数组，使得数组中的数字之和为 x
    数组中的每一个数字都不是随意选取的，而是有特定的规则
    比如，可以通过一个生成器来生成，也可以是在一个自定义的数组中选取，
    包含这样的数字的列表称为「候选列表」 (Candidate List)

    我们可以对候选列表进行的操作有：
    1. 获取一个元素
    2. 获取一个元素的相邻元素（前一个或者后一个）
    3. 判断某个数字是否是候选列表中的元素
    4. 查找候选列表中与给定数字大小最接近的元素

    候选列表里面的元素不能重复，乍看上去是一个集合，但是又不是集合，因为有先后顺序。（集合是无序的）
    先后顺序其实就是按照数字的值由小到大排序后的顺序

    如果把候选列表中的数字换成其他的东西，比如「字符串」，那么只要定义「字符串」的「排序规则」
    就可以保证上述的4个操作仍然有意义。

    这个称作「候选列表」的数据结构，就是解决「装仓问题」的关键

    装仓问题描述：
    现有一个大小为x的仓库，和一个包含N个元素的候选列表L, 只使用L中的元素装填仓库，要求装满仓库，给出装填列表
    L中的元素具有数字属性，代表所占的空间大小。为简单起见，特规定L中的元素就是数字，没有其他属性

    待填空间称为「隙」，填入的元素称为「粒」，元素数字属性的大小就是「粒的大小」
    优先使用「大粒」填入「隙」，可以使「隙」减小得更快！
    `solv_n(x)`就是根据「隙」的大小x，求出尽量大的粒的大小n
    '''
    lis = []
    while x:
        print(f'x: {x}')
        n = solv_n(x)
        x -= n*(n+1) // 2
        lis.append(n)
    print(f'lis: {lis}')

    return lis

def construct_str(chars: str, counts: List[int]) -> str:
    '''
    额外要求：chars里面不能出现重复字符

    构造题目要求的字符串，其回文子串的个数有x个

    构造方法很简单：使用装仓算法计算出每个「粒」的大小,
    一个粒是由'同种类的字符'构成的字符串，粒的大小就是字符串的长度，如 字符串'aaaa'对应的粒的大小是4
    只要按照counts里面的数字依次选取相应个数的字符拼接起来就可以
    假设 chars = 'abc'
    如 [7, 1, 1] 对应 7 个chars[0], 1个chars[1], 1个chars[2]
    拼好后是：'aaaaaaabc'
    counts里面的数字一般会越来越小，像3个字符的这种，不用担心`counts[i] == counts[i+3]`
    这种情况不会出现。而且即便出现也未必保证「第一个只包含'a'的粒」 和 「第二个只包含'a'的粒」之间的字串是回文的
    如'aaabcaaa' 因为 'bc'的存在，整体不会回文

    只要保证**依次**使用"abc"中的字符，永远也不可能在「粒」之外产生新的回文字串
    「a..b..c..的顺序」想要对称只能存在「c..b..a的顺序」！
    这就是这个题目至少需要3个字符的原因！
    如果只提供两个，a..b 和 b..a的顺序都会出现，不易控制「粒之外的回文」是否产生

    再次强调：依次使用"abc"中的字符，永远也不可能在「粒」之外产生新的回文字串

    这就是使用装仓算法解决「构造指定回文子串个数的字符串」问题的关键

    当然，需要说明的是，这道题目的解法不唯一，结果也不唯一。
    我只是通过控制「依次使用"abc"中的字符」这一条件，降低了问题的复杂度而已
    如果放弃此条件，或许也有办法解决，但我还没有想到。
    例子：
    'aba' 中的回文子串的个数是4，但是违背了「依次使用"abc"中的字符」
    '''
    # n = len(counts)
    m = len(chars)
    res = ""
    for idx, cnt in enumerate(counts):
        ch = chars[(idx) % m]  # 依次使用！
        res += ch * cnt  # 拼接过程（装填过程）

    return res

if __name__ == '__main__':
    x = 1024
    s = 'abc'
    cnts = binning_algo(x)
    str = construct_str(s, cnts)
    print(str)
